1. Field
Embodiments of the present invention relate to a system and method for storing sparse matrices, and more particularly, to variations of the compressed row storage (CRS) format for storing and retrieval of sparse matrices in a computing device.
2. Related Art
Many applications in science and engineering require the solution to large matrix equations, such as computational fluid dynamics, electromagnetics, geophysical exploration, economics, linear programming, astronomy, chemistry, and structural analysis. Solving a large matrix equation is computationally expensive. Many computer resources are required and the elapse of time-to-solution can be prohibitively long. Decreasing solution times may allow the same analysis to be conducted in less time or higher-resolution analysis to be conducted in the same amount of time.
For large eigenvalue problems, if the coefficient matrix A is sparse (contains mostly zeros), the problems can be most efficiently solved if the zero elements of matrix A are neither manipulated nor stored. Sparse storage schemes allocate contiguous storage in memory for the nonzero elements of the matrix, using a scheme for knowing where the non-zero elements fit into the full matrix. There are many existing schemes for sparse matrix storage. Some are based on assumptions about the distribution of non-zeros within the matrix.
One method typically used for storing large sparse matrices in the aforementioned applications is the compressed row storage (CRS) format. The CRS format does not make assumptions about the distribution of non-zeros within the matrix, but also does not store any unnecessary matrix elements. The CRS format takes the nonzero elements of the matrix in row-major order and places them in contiguous memory locations. Three vectors or one-dimensional arrays are created from the matrix: one for storing the nonzero elements (data array “a”) of the matrix, one for storing the column addresses (col_idx array) of the nonzero elements, and one for the locations in the data array “a” that contain the first non-zero element of a row (row_ptr array). The last value in the row_ptr array, or row_ptr(n+1), is assigned the number of nonzeros (nnz) in the matrix plus one, where “n” is the rank of the matrix. So, instead of requiring n2 storage locations, the CRS format only stores 2nnz+n+1 storage locations.
Below is an example matrix and its resulting arrays:
      a    =          [                                                  a              1                                                          a              2                                                          a              3                                                          a              4                                                          a              5                                                          a              6                                                          a              7                                                          a              8                                                          a              9                                                          a              10                                                          a              11                                          ]            A    =          [                                                  a              1                                                          a              2                                            0                                0                                0                                              a              3                                                            0                                              a              4                                            0                                0                                0                                0                                                0                                0                                0                                              a              5                                                          a              6                                            0                                                0                                0                                0                                0                                              a              7                                                          a              8                                                            0                                              a              9                                            0                                              a              10                                            0                                0                                                0                                0                                0                                0                                              a              11                                            0                              ]            col_idx    =          [                                    1                                2                                6                                2                                4                                5                                5                                6                                2                                4                                5                              ]            row_ptr    =          [                                    1                                4                                5                                7                                9                                11                                12                              ]      
So col_idx stores the matrix column addresses of the elements of data array “a”, and the row_ptr array stores the locations in data array “a” of the first non-zero elements in a row, with row_idx(n+1)=nnz+1.
The CRS format, as described above, is somewhat inefficient, since it requires the use of non-sequential memory, specifically the row_ptr array, to access the matrix data.